1. Field of the Invention
The present invention relates to a polygon data sorting method, and a polygon data sorting system therefor. In particular, the present invention pertains to a polygon data sorting method, for a three-dimensional polygon computer graphic (CG) system, whereby a plurality of polygons are displayed by using depth values for the polygons, and to a polygon data sorting system therefor.
2. Related Arts
The sorting of polygon data is required in order to perform the removal of hidden surface in a three-dimensional polygon CG system, i.e., to remove hidden polygonal surfaces in consonance with a display priority when polygons are superimposed on a display device.
One of the methods employed for displaying polygons involves the use depth values (Z values) to determine the order in which the polygons are displayed. With this method, rearrangement of the polygon data must be performed in consonance with the depth values.
FIGS. 1, 2 and 3 are diagrams for explaining the rearrangement of polygons. In FIG. 1 example polygon data are shown. This polygon has three-dimensional coordinate points P0, P1 and P2 and a representative point Pr for these three points. The point Pr is acquired as the average value for the other three points.
The representative Z value for the point Pr is the average value obtained for the depth values of the polygon, and generally, polygon sorting is performed by using the representative Z value. FIG. 2 is a diagram for explaining this process. Assuming that polygons C, B and A are input in the order of registration, and that their representative Z values are 16, 17 and 23, the polygons are sorted and rearranged in the descending order of their representative values. As a result, the polygons are output in the order of A, B and C.
FIG. 3 is a diagram showing example polygons that are sorted and rearranged described in the descending order of their representative Z values. In FIG. 3, a plurality of polygons A, B, C, D, . . . and N are arranged in consonance with distances (representative Z values Z1, Z2, . . . and Zn) in the direction of the depth relative to the Z axis of the three-dimensional coordinates. The polygons are displayed in order as they are arranged in this manner.
Various methods, such as the one described above, have been proposed for rearranging polygon data. One method, called a quick sorting method, takes into account the fact that sorting can be performed fast by using hardware.
According to the quick sorting method, however, a problem has arisen in that the overhead for a data transfer circuit is increased because of the need for frequent data exchanges between memory areas. An additional problem that has arisen is that execution speeds vary greatly, depending on the changes in the representative Z values.
Another method that more effectively performs the exchange of data is a distribution method. This method, however, requires a greater memory capacity.